package com.java.basis.sort;

/**
 * 二分查找：二分查找的前提就是已经拍好了顺序
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        int target = 48;
        int idx = binarySearch(array, target);
        System.out.println("idx = " + idx);
    }
    //二分查找，找到返回元素索引，找不到返回-1
    private static int binarySearch(int[] a, int t) {
//        int l = 0;
//        int r = a.length - 1;
//        int m;
        int l = 0, r = a.length - 1, m;
        while (l <= r) {
            //中间值优化
            //第一种
//            m = (l + r) / 2;// l/2 + r/2  ==> l + (-l/2 + r/2)  ==> l + (r-l)/2,所以获取中间值可以使用以下代替，防止l+ r大于最大值，导致溢出
//            m = l + (r - l) / 2;//第一种
            //第二种使用位运算，向右移动一位
            m = (l + r) >>> 1;//第二种，这种运算更加的快
            if (a[m] == t) {
                return m;
            } else if (a[m] > t) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

}
